package com.chenken;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import com.chenken.printer.BinaryTreeInfo;

/**
 * 二叉搜索树 Binary Search Tree 简称BST  ,又称为二叉查找树，二叉排序树
 * 特性：
 * 左子节点的所有元素都要比它的父节点要小
 * 右子节点的所有 元素都要比它的父节点要大
 * 它的左右子树也是一颗二叉搜索树
 * 二叉搜索树可以大大提高数据搜索的效率
 * 它的元素必须具有可比较性，元素不允许为null
 * 它没有索引
 */
public class BinarySearchTree<E> implements BinaryTreeInfo{

	private int size;
	
	/**
	 * 根节点
	 */
	private Node<E> root;
	
	/**
	 * 比较器
	 */
	private Comparator<E> comparator;
	
	public BinarySearchTree() {
		this(null);
	}
	
	public BinarySearchTree(Comparator<E> comparator) {
		this.comparator = comparator;
	}
	
	public int size() {
		return size;
	}
	
	public boolean isEmpty() {
		return size == 0;
	}
	
	public void clear() {
		root = null;
		size = 0;
	}
	
	public void add(E element){
		elementNotNullCheck(element);
		//	如果根节点不存在，该元素为根节点
		if(root == null) {
			root = new Node<>(element, null);
			size++;
			return;
		}
		//	找到父节点
		Node<E> node = root;
		Node<E> parent = root;
		int cmp = 0;
		while (node!=null) {
			cmp = compare(element, node.element);
			parent = node;
			if(cmp > 0) {
				node = node.right;
			}else if(cmp < 0) {
				node = node.left;
			}else {
				/**
				 * 树中已存在该元素，将该元素覆盖，返回
				 * 元素可能是一个对象，对象的可比较的属性相等，但是其他属性不相等，所以需要覆盖
				 */
				node.element = element;
				return;
			}
		}
		//	看看插入到父节点的左还是右
		Node<E> newNode = new Node<>(element, parent);
		if(cmp > 0) {
			parent.right = newNode;
		}else {
			parent.left = newNode;
		}
		size++;
	}
	
	
	@SuppressWarnings("unchecked")
	private int compare(E e1,E e2) {
		//	如果传了比较器，就按照比较器的逻辑来比
		if(comparator != null) {
			return comparator.compare(e1, e2);
		}
		//	如果没传比较器，由于二叉搜索树的所有元素必须具有可比较性，这里强转e1为Comparable类型
		return ((Comparable<E>)e1).compareTo(e2);
	}
	
	public void remove(E element) {
		if(element == null) {
			return;
		}
		if(compare(root.element, element) == 0) {
			remove(root);
		} else{
			Node<E> node = node(element);
			if(node != null) {
				remove(node);
			}
		}
	}
	
	/**
	 * 根据element找到节点
	 * @param element
	 * @return
	 */
	private Node<E> node(E element){
		Node<E> node = root;
		while(node != null) {
			int comp = compare(node.element,element);
			if(comp == 0) {
				return node;
			}
			if(comp > 0) {
				node = node.left;
			}else{
				node = node.right;
			}
		}
		return node;
	}
	
	private void remove(Node<E> node) {
		size--;
		//node是度为2的节点
		if(node.hasTwoChildren()) {
			Node<E> successor = successor(node);//找到后继节点
			node.element = successor.element;//将值替换
			node = successor;	//将node指向successor
		}
		//node是叶子节点
		if(node.isLeaf()) {
			removeLeaf(node);
			return;
		}
		//node是度为1的节点
		if(node.hasOneChild()) {
			removeOneChildNode(node);
			return;
		}
	}
	
	/**
	 * 删除叶子节点
	 * @param node
	 */
	private void removeLeaf(Node<E> node) {
		if(node.parent == null) {
			root = null;
		}else {
			if(node.parent.left == node) {
				node.parent.left = null;
			}else {
				node.parent.right = null;
			}
		}
	}
	/**
	 * 删除度为1的节点
	 * @param node
	 */
	private void removeOneChildNode(Node<E> node) {
		Node<E> replacement = node.left !=null ?node.left:node.right;
		replacement.parent = node.parent;
		if(node.parent == null) {	//node是度为1的根节点
			root = replacement;
		}else if(node.parent.left == node) {
			node.parent.left = replacement;
		}else {
			node.parent.right = replacement;
		}
	}
	
	/**
	 * 是否包含元素
	 * @param element
	 * @return
	 */
	public boolean contain(E element) {
		return node(element) != null;
	}
	
	private void elementNotNullCheck(E element) {
		if(element == null) {
			throw new IllegalArgumentException("element must not be null");
		}
	}
	
	/**
	 * 前序遍历-非递归   根左右  第一种
	 * @param visitor
	 */
	public void preorderTraversal2(Visitor<E> visitor) {
		if(root == null || visitor == null) return;
		System.out.println("前序遍历-非递归-第一种");
		
		Node<E> node = root;
		Stack<Node<E>> stack = new Stack<Node<E>>();
		while (true) {
			if(node != null) {
				if(visitor.visit(node.element)) return;
				if(node.right != null) {
					stack.push(node.right);
				}
				//向左走
				node = node.left;
			}else {
				if(stack.isEmpty()) {
					return;
				}
				node = stack.pop();
			}
		}
	}
	
	/**
	 * 前序遍历-非递归   根左右  第二种
	 * @param visitor
	 */
	public void preorderTraversal3(Visitor<E> visitor) {
		if(root == null || visitor == null) return;
		System.out.println("前序遍历-非递归-第二种");
		
		Stack<Node<E>> stack = new Stack<Node<E>>();
		stack.push(root);
		while (!stack.isEmpty()) {
			Node<E> pop = stack.pop();//弹出栈顶元素并访问
			if(visitor.visit(pop.element)) return;
			if(pop.right != null) {
				stack.push(pop.right);
			}
			if(pop.left != null) {
				stack.push(pop.left);
			}
		}
	}
	
	/**
	 * 前序遍历-递归
	 */
	public void preorderTraversal(Visitor<E> visitor) {
		System.out.println("前序遍历-递归");
		if(visitor == null) {
			return;
		}
		preorderTraversal(root,visitor);
	}
	
	private void preorderTraversal(Node<E> node,Visitor<E> visitor) {
		if(node == null || visitor.stop) {
			return;
		}
		visitor.stop = visitor.visit(node.element);
		preorderTraversal(node.left,visitor);
		preorderTraversal(node.right,visitor);
	}
	
	/**
	 * 中序遍历-非递归   左根右
	 * @param visitor
	 */
	public void inorderTraversal2(Visitor<E> visitor) {
		if(root == null || visitor == null) return;
		System.out.println("中序遍历-非递归");
		Stack<Node<E>> stack = new Stack<Node<E>>();
		Node<E> node = root;
		while(true) {
			if(node != null) {
				stack.push(node);
				node = node.left;
			}else {
				if(stack.isEmpty()) {
					return;
				}
				node = stack.pop();
				if(visitor.visit(node.element)) return;
				node = node.right;
			}
		}
	}
	
	/**
	 * 中序遍历-递归
	 */
	public void inorderTraversal(Visitor<E> visitor) {
		System.out.println("中序遍历-递归");
		if(visitor == null) {
			return;
		}
		inorderTraversal(root,visitor);
	}
	
	private void inorderTraversal(Node<E> node,Visitor<E> visitor) {
		if(node == null || visitor.stop) {
			return;
		}
		inorderTraversal(node.left,visitor);
		if(visitor.stop) return;
		visitor.stop = visitor.visit(node.element);
		inorderTraversal(node.right,visitor);
	}
	
	/**
	 * 后序遍历-非递归
	 * @param visitor
	 */
	public void postorderTraversal2(Visitor<E> visitor) {
		if(root == null || visitor == null) return;
		System.out.println("后序遍历-非递归");
		Stack<Node<E>> stack = new Stack<Node<E>>();
		stack.push(root);
		
		Node<E> prePopNode = null;
		while(!stack.isEmpty()) {
			Node<E> node = stack.peek();
			if(node.isLeaf() || (prePopNode !=null && prePopNode.parent == node)) {
				prePopNode = stack.pop();
				if(visitor.visit(prePopNode.element)) return;
			}else {
				if(node.right!=null) {
					stack.push(node.right);
				}
				if(node.left!=null) {
					stack.push(node.left);
				}
			}
		}
	}
	
	/**
	 * 后序遍历-递归
	 */
	public void postorderTraversal(Visitor<E> visitor) {
		System.out.println("后序遍历-递归");
		if(visitor == null) {
			return;
		}
		postorderTraversal(root,visitor);
	}
	
	private void postorderTraversal(Node<E> node,Visitor<E> visitor) {
		if(node == null || visitor.stop) {
			return;
		}
		postorderTraversal(node.left,visitor);
		postorderTraversal(node.right,visitor);
		if(visitor.stop) return;
		visitor.stop = visitor.visit(node.element);
	}
	
	/**
	 * 层序遍历
	*/
	public void levelOrderTraversal(Visitor<E> visitor) {
		System.out.println("层序遍历");
		if(root == null || visitor == null) {
			return;
		}
		Queue<Node<E>> queue = new LinkedList<Node<E>>();
		queue.offer(root);//将根节点入队
		while(!queue.isEmpty()) {
			Node<E> node = queue.poll();//将队头出队
			if(visitor.visit(node.element)) {	//访问
				return;
			} 
			if(node.left!=null) {
				queue.offer(node.left);//将左子节点入队
			}
			if(node.right!=null) {
				queue.offer(node.right);//将右子节点入队
			}
		}
	}
	
	public int height() {
		if(root == null) {
			return 0;
		}
		//树的高度
		int height = 0;
		Queue<Node<E>> queue = new LinkedList<Node<E>>();
		queue.offer(root);//将根节点入队
		//	存储每一层的元素数量,根节点入队,层数为1
		int levelSize = 1;
		while(!queue.isEmpty()) {
			Node<E> node = queue.poll();//将队头出队
			levelSize--;
			if(node.left!=null) {
				queue.offer(node.left);//将左子节点入队
			}
			if(node.right!=null) {
				queue.offer(node.right);//将右子节点入队
			}
			if(levelSize == 0) {	//	根节点出队后，说明第一层访问完毕
				levelSize = queue.size();//将下一层的数量赋值给levelSize
				height++;//	一层访问完毕，高度加一
			}
		}
		return height;
	}
	
	/**
	 * 找到前驱节点
	 * 中序遍历时的前一个节点
	 * @param node
	 * @return
	 */
	private Node<E> predecessor(Node<E> node){
		if(node == null) {
			return null;
		}
		Node<E> p = node.left;
		if(p != null) {
			while(node.right != null) {
				p = p.right;
			}
			return p;
		}
		while(node.parent !=null && node == node.parent.left) {
			node = node.parent;
		}
		return node.parent;
	}
	
	/**
	 * 找到后继节点
	 * 中序遍历时的后前一个节点
	 * @param node
	 * @return
	 */
	private Node<E> successor(Node<E> node){
		if(node == null) {
			return null;
		}
		Node<E> p = node.right;
		if(p != null) {
			while(p.left != null) {
				p = p.left;
			}
			return p;
		}
		while(node.parent !=null && node == node.parent.right) {
			node = node.parent;
		}
		return node.parent;
	}
	
	/**
	 * 判断是否是完全二叉树
	 * 如果树为null,返回false
	 * 如果树不为null，开始层序遍历二叉树
	 * 如果 node.left!=null && node.right!=null，将节点的左右子节点入队
	 * 如果 node.left == null && node.right!=null 返回false
	 * 如果node.left !=null && node.right == null或node.left ==null && node.right == null
	 * 那从这个节点开始，接下来的所有节点都应该为叶子节点，否则就返回false
	 * 
	 * 遍历结束,返回true
	 * @return
	 */
	public boolean isComplete() {
		if(root == null) {
			return false;
		}
		Queue<Node<E>> queue = new LinkedList<Node<E>>();
		queue.offer(root);//将根节点入队
		
		Node<E> node = root;
		boolean isLeaf = false;
		while (!queue.isEmpty()) {
			node = queue.poll();
			if(isLeaf && !node.isLeaf()) {
				return false;
			}
			if(node.left != null) {
				queue.offer(node.left);
				if(node.right != null) {
					queue.offer(node.right);//left !=null && right != null
				}else {
					isLeaf = true;//left !=null && right == null
				}
			}else {
				if(node.right == null) {
					isLeaf = true;//left ==null && right == null
				}else{
					return false;//left ==null && right != null
				}
			}
		}
		return true;
	}
	
	/**
	 * 翻转二叉树
	 */
	public void filpBinaryTree() {
		if(root == null) {
			return;
		}
		System.out.println("------------翻转二叉树------------");
		Queue<Node<E>> queue = new LinkedList<Node<E>>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			Node<E> node = queue.poll();
			
			Node<E> left = node.left;
			Node<E> right = node.right;
			node.left = right;
			node.right = left;
			
			if(node.left != null) {
				queue.offer(node.left);
			}
			if(node.right != null) {
				queue.offer(node.right);
			}
		}
	}
	
	public static abstract class Visitor<E>{
		
		boolean stop = false;
		
		abstract boolean visit(E element);
	}
	
	private static class Node<E>{
		E element;
		Node<E> left;
		Node<E> right;
		Node<E> parent;
		public Node(E element, Node<E> parent) {
			this.element = element;
			this.parent = parent;
		}
		
		public boolean hasOneChild() {
			return (left != null && right == null) || (left == null && right != null);
		}
		
		public boolean hasTwoChildren() {
			return left != null && right != null;
		}
		
		/**
		 * 是否是叶子节点
		 * @return
		 */
		public boolean isLeaf() {
			return left == null && right == null;
		}
		
	}


	@Override
	public Object root() {
		return root;
	}

	@Override
	public Object left(Object node) {
		return ((Node<E>)node).left;
	}

	@Override
	public Object right(Object node) {
		return ((Node<E>)node).right;
	}

	@Override
	public Object string(Object node) {
		return ((Node<E>)node).element;
	}
	
}
